package com.tys.algorithm.advanced.test.class14;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * 并差集
 * a b c d e f
 * 每个小样本在自己的集合里{a} {b} {c} {d} {e} {f}
 * 1.查询两个样本是否在一个集合
 * boolean issameSet(a, e)
 * 2.a所在集合全体和e所在集合全体合成一个集合
 * void union(a,e)
 */
public class Code05_UnionFind {

    public static class Node<V> {
        V value;

        public Node(V v) {
            value = v;
        }
    }

    public static class UnionFind<V> {
        public HashMap<V, Node<V>> nodes; //样本对应自己包装后的表
        public HashMap<Node<V>, Node<V>> parents; //父子关系表
        public HashMap<Node<V>, Integer> sizeMap; //代表节点记录大小

        public UnionFind(List<V> values) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            //样本生成表
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node); //加入node
                parents.put(node, node); //自己指向自己
                sizeMap.put(node, 1); //集合个数1
            }
        }

        // 给你一个节点，请你往上到不能再往上，把代表返回
        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            //cur到顶退出循环
            while (cur != parents.get(cur)) {
                //放入栈
                path.push(cur);
                //找cur的父
                cur = parents.get(cur);
            }
            //将栈中的节点挂到代表节点：变扁平
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            return cur;
        }

        //a和b是否在一个集合
        public boolean isSameSet(V a, V b) {
            //代表节点是同一个就是在一个集合中
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        //a所在集合和b所在集合合并
        public void union(V a, V b) {
            //a的代表节点
            Node<V> aHead = findFather(nodes.get(a));
            //b的代表节点
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) { //不是一个集合就合并
                //a集合大小
                int aSetSize = sizeMap.get(aHead);
                //b集合大小
                int bSetSize = sizeMap.get(bHead);
                //找到大集合的代表节点
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                //找到小集合的代表节点
                Node<V> small = big == aHead ? bHead : aHead;
                //小集合的头指向大集合：小集合父亲设置为大集合
                parents.put(small, big);
                //设置大集合的大小为：合并后的总数
                sizeMap.put(big, aSetSize + bSetSize);
                //移除小集合大小：知道目前合并后有几个集合
                sizeMap.remove(small);
            }
        }

        public int sets() {
            return sizeMap.size();
        }

    }
}
